package com.company.剑指offer每日刷题.普通版;

/**
 * 剑指 Offer 63. 股票的最大利润
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 *
 *
 *
 * 示例 1:
 *
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
 *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
 * 示例 2:
 *
 * 输入: [7,6,4,3,1]
 * 输出: 0
 * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 *
 *
 * 限制：
 *
 * 0 <= 数组长度 <= 10^5
 * */
public class MaxProfit {
    /**
     *
     * 方法：动态规划
     * 思路；
     *      定义：令 截止第i天的可获得最大利润是： dp[i]，表示的是前i天的子数组产生的可获得的最大利润;
     *          令 第i天的价格是 price[i];
     *      状态转移方程：
     *          前i日最大利润 = max(前(i-1)日的最大利润, 第i日价格 - 前i日的最低价格)
     *          dp[i] = max(dp[i-1],price[i] - min(price[0:i]))
     *      初始状态：
     *          dp[0] = 0，也就是，首日的利润是0
     *      优化：
     *          (1)可以通过一个临时变量代替 min(price[0:i]) 存放过去所有天的价格最低值，作为购买成本。每天更新这个最低成本就可以了
     *          dp[i] = max(dp[i-1],price[i] - minCost)
     *          (2)因为前i日的最大利润之和当天的价格和前(i-1)日的最大利润有关，所以用一个变量profit来存储这个利润就行了
     *      变形：
     *          profit = max(profit,price[i] - minCost)
     * */
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int profit = 0,minCost = prices[0];
        for (int i = 0; i < prices.length; i++) {
            minCost = Math.min(prices[i],minCost);
            profit = Math.max(profit,prices[i] - minCost);
        }
        return profit;
    }
}
